package com.gitee.swsk33.algorithms.tree.binarytree;

import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树类
 */
@Getter
@Setter
@NoArgsConstructor
public class BinaryTree<T> {

	/**
	 * 二叉树根节点
	 */
	private TreeNode<T> root;

	/**
	 * 以一个值作为根节点的值构造一个二叉树
	 *
	 * @param data 根节点值
	 */
	public BinaryTree(T data) {
		this.root = new TreeNode<>(data);
	}

	/**
	 * 先序遍历二叉树-递归部分
	 *
	 * @param root   传入待遍历二叉树的根结点
	 * @param result 用于储存遍历结果的列表对象
	 */
	private void preorderTraversal(TreeNode<T> root, List<T> result) {
		if (root != null) {
			// 先把根结点值计入结果
			result.add(root.getData());
			// 然后向下递归先序遍历左子树，继续向下传入结果列表对象
			preorderTraversal(root.getLeft(), result);
			// 最后向下递归先序遍历右子树，继续向下传入结果列表对象
			preorderTraversal(root.getRight(), result);
		}
	}

	/**
	 * 先序遍历二叉树-启动部分
	 *
	 * @return 自身的先序遍历结果
	 */
	public List<T> preorderTraversal() {
		List<T> result = new ArrayList<>();
		preorderTraversal(root, result);
		return result;
	}

	/**
	 * 中序遍历二叉树-递归部分
	 *
	 * @param root   传入待遍历二叉树的根结点
	 * @param result 用于储存遍历结果的列表对象
	 */
	private void inorderTraversal(TreeNode<T> root, List<T> result) {
		if (root != null) {
			// 先向下递归中序遍历左子树，继续向下传入结果列表对象
			inorderTraversal(root.getLeft(), result);
			// 然后把根结点值计入结果
			result.add(root.getData());
			// 最后向下递归中序遍历右子树，继续向下传入结果列表对象
			inorderTraversal(root.getRight(), result);
		}
	}

	/**
	 * 中序遍历二叉树-启动部分
	 *
	 * @return 自身的中序遍历结果
	 */
	public List<T> inorderTraversal() {
		List<T> result = new ArrayList<>();
		inorderTraversal(root, result);
		return result;
	}

	/**
	 * 后序遍历二叉树-递归部分
	 *
	 * @param root   传入待遍历二叉树的根结点
	 * @param result 用于储存遍历结果的列表对象
	 */
	private void postorderTraversal(TreeNode<T> root, List<T> result) {
		if (root != null) {
			// 先向下递归后序遍历左子树，继续向下传入结果列表对象
			postorderTraversal(root.getLeft(), result);
			// 然后向下递归后序遍历右子树，继续向下传入结果列表对象
			postorderTraversal(root.getRight(), result);
			// 最后把根结点值计入结果
			result.add(root.getData());
		}
	}

	/**
	 * 后序遍历二叉树-启动部分
	 *
	 * @return 自身的后序遍历结果
	 */
	public List<T> postorderTraversal() {
		List<T> result = new ArrayList<>();
		postorderTraversal(root, result);
		return result;
	}

}